package com.atwulidun.graph.adjacentlist;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class GraphDemo {
    public static void main(String[] args) {
        int[] verVals = {0,1,2,3,4,5};
        int[][] edges = {{0,1,100},{0,2,200},{0,3,300},{1,4,400},{2,5,500},{4,5,600},{5,3,700}};
        Graph graph = new Graph(verVals, edges, true);
//        graph.show();
        // 广度优先遍历
//        graph.bfs();//0->1->2->3->4->5->
        // 深度优先遍历
        graph.dfs();//0->1->4->5->3->2->
    }
}

class Graph {
    // 存放顶点的数组
    private Vertex[] vertices;
    // 是否为有向图的判断(true为有向图；false为无向图)
    private boolean isDirected;

    // 图的初始化：要分为有向图和无向图
    // 注意：初始化时要保证每一个vertex只有一个引用！！！！！！！！
    /**
     * @param verVals
     * 每个顶点对应的值
     * @param edges
     * n * 3的二维数组，若为有向图，分别存放该边对应的起始顶点，终点顶点以及权值
     * 对于无向图而言，edges[i][0]和edges[i][1]的位置可以随便互换
     * @param isDirected
     * 确定该图是否为有向图
     */
    public Graph(int[] verVals, int[][] edges, boolean isDirected) {
        this.isDirected = isDirected;
        // 对vertices数组进行初始化
        vertices = new Vertex[verVals.length];
        for (int i = 0; i < vertices.length; i++) {
            // 这里是保证每个vertex只有一个引用，下面在添加边结点的时候用到的也是这里的vertex，不能再根据vertex.verVal重新new！！！！
            vertices[i] = new Vertex(verVals[i]);
        }
        for (int i = 0; i < vertices.length; i++) {
            // 接下来要将edges添加到vertex的后面
            // 首先定义一个cur指针，指向最尾部的edge
            Edge curEdge = null;
            for (int j = 0; j < edges.length; j++) {
                // 无论有向图还是无向图都要走下面这个if判断
                if (verVals[i] == edges[j][0]) {
                    // 还要判断vertex的edgeHead是否为空
                    if (vertices[i].getEdgeHead() == null) {
                        // 若为空，则先创建一个edge
                        // 注意：重新new Vertex(edges[j][1])是不对的！！！！！！！
//                        vertices[i].setEdgeHead(new Edge(edges[j][2], new Vertex(edges[j][1])));
                        vertices[i].setEdgeHead(new Edge(edges[j][2], findVertexByVerVal(edges[j][1])));
                        // 将cur指向边链表的头结点
                        curEdge = vertices[i].getEdgeHead();
                    } else {
                        // 如果当前边链表的头结点不为空
                        while (curEdge.getNextEdge() != null) {
                            curEdge = curEdge.getNextEdge();
                        }
                        curEdge.setNextEdge(new Edge(edges[j][2], findVertexByVerVal(edges[j][1])));
                        // 将curEdge指向边链表的最后一个结点
                        curEdge.setNextEdge(curEdge.getNextEdge());
                    }
                }
                // 下面是无向图才需要走
                if (!isDirected && verVals[i] == edges[j][1]) {
                    // 还要判断vertex的edgeHead是否为空
                    if (vertices[i].getEdgeHead() == null) {
                        // 若为空，则先创建一个edge
                        vertices[i].setEdgeHead(new Edge(edges[j][2], findVertexByVerVal(edges[j][0])));
                        // 将cur指向边链表的头结点
                        curEdge = vertices[i].getEdgeHead();
                    } else {
                        // 如果当前边链表的头结点不为空
                        while (curEdge.getNextEdge() != null) {
                            curEdge = curEdge.getNextEdge();
                        }
                        curEdge.setNextEdge(new Edge(edges[j][2], findVertexByVerVal(edges[j][0])));
                        // 将curEdge指向边链表的最后一个结点
                        curEdge.setNextEdge(curEdge.getNextEdge());
                    }
                }
            }
        }
    }

    // 根据vertex的verVal查找对应vertex的方法
    private Vertex findVertexByVerVal(int verVal) {
        if (vertices != null && vertices.length != 0) {
            for (Vertex vertex : vertices) {
                if (vertex.getVerVal() == verVal) {
                    return vertex;
                }
            }
        }
        return null;
    }

    // 以下两个为广度优先对应的方法
    // 一、广度优先遍历(用队列)
    // 能进入该方法的vertex都是未经访问过的
    private void bfs(Vertex vertex) {
        // 首先将该顶点的值打印出来
        System.out.print(vertex.getVerVal() + "->");
        // 将该顶点设置为已经被访问
        vertex.setIsVisited(true);
        // 创建一个队列
        Queue<Vertex> queue = new LinkedList<>();
        // 将该顶点放入队列中
        queue.add(vertex);
        while (!queue.isEmpty()) {
            // 获取队列的头元素
            Vertex front = queue.remove();
            // 获取头元素对应的边链表的头结点
            Edge headEdge = front.getEdgeHead();
            // 对front进行横向遍历
            while (headEdge != null) {
                // 如果当前边的尾部顶点没有被访问过
                if (!headEdge.getRearVer().getIsVisited()) {
                    // 首先输出当前边尾部顶点的值
                    System.out.print(headEdge.getRearVer().getVerVal() + "->");
                    // 将当前边尾部顶点设置为已经被访问
                    headEdge.getRearVer().setIsVisited(true);
                    // 将当前边尾部顶点加入队列中
                    queue.add(headEdge.getRearVer());
                }
                // 移向下一条边
                headEdge = headEdge.getNextEdge();
            }
        }
    }

    // 二、如果是非联通图，还需要对上面的方法进行一个重载
    public void bfs() {
        if (vertices == null || vertices.length == 0) {
            System.out.println("图为空，不能遍历！！");
            return;
        }
        // 对vertices进行遍历
        for (Vertex vertex : vertices) {
            // 如果vertex不为空且未被访问过
            if (vertex != null && !vertex.getIsVisited()) {
                bfs(vertex);
            }
        }
    }

    // 以下三个为深度优先遍历对应的方法
    // 一、深度优先遍历(用栈，非递归)
    private void dfs1(Vertex vertex) {
        // 将当前顶点的信息打印出来
        System.out.print(vertex.getVerVal() + "->");
        // 将当前顶点设置为已经被访问
        vertex.setIsVisited(true);
        // 创建一个栈
        Deque<Vertex> stack = new LinkedList<>();
        // 将当前顶点压入栈中
        stack.push(vertex);
        while (!stack.isEmpty()) {
            // 获取栈顶的元素
            Vertex top = stack.pop();
            // 获取栈顶元素对应边链表的头结点
            Edge headEdge = top.getEdgeHead();
            while (headEdge != null) {
                // 如果当前边的末尾顶点没有被访问过
                if (!headEdge.getRearVer().getIsVisited()) {
                    // 打印出当前边末尾顶点的值
                    System.out.print(headEdge.getRearVer().getVerVal() + "->");
                    // 将该顶点设置为已经被访问
                    headEdge.getRearVer().setIsVisited(true);
                    // 将该顶点压入栈中
                    stack.push(headEdge.getRearVer());
                    // 找到第一个未被访问过的顶点，这里可以直接break了
                    break;
                }
                // 找下一条边
                headEdge = headEdge.getNextEdge();
            }
        }
    }
    // 二、深度优先遍历(递归)
    private void dfs2(Vertex vertex) {
        // 将当前顶点的信息打印出来
        System.out.print(vertex.getVerVal() + "->");
        // 将当前顶点设置为已经被访问
        vertex.setIsVisited(true);
        // 获取该顶点对应边链表的头结点
        Edge headEdge = vertex.getEdgeHead();
        while (headEdge != null) {
            // 如果当前边的末尾顶点没有被访问过
            if (!headEdge.getRearVer().getIsVisited()) {
                // 进入下一层的递归
                dfs2(headEdge.getRearVer());
                break;
            }
            // 找下一条边
            headEdge = headEdge.getNextEdge();
        }
    }
    // 三、如果是非联通图，还需要对上面的两个方法进行一个封装
    public void dfs() {
        if (vertices == null || vertices.length == 0) {
            System.out.println("图为空，不能遍历！！");
            return;
        }
        // 对vertices进行遍历
        for (Vertex vertex : vertices) {
            // 如果vertex不为空且未被访问过
            if (vertex != null && !vertex.getIsVisited()) {
                dfs1(vertex);
//                dfs2(vertex);
            }
        }
    }

    // 普通遍历图的方法
    public void show() {
        if (vertices == null || vertices.length == 0) {
            System.out.println("图为空，不能遍历！！");
            return;
        }
        for (Vertex vertex : vertices) {
            // 先把当前顶点的值输出来
            System.out.print(vertex.getVerVal() + "->");
            // 获取该顶点对应边链表的头结点
            Edge headEdge = vertex.getEdgeHead();
            while (headEdge != null) {
                // 输出当前边对应的权值
                System.out.print("(" + headEdge.getWeight() + ")");
                // 输出当前边末尾顶点的值
                System.out.print(headEdge.getRearVer().getVerVal() + "->");
                // 找下一条边
                headEdge = headEdge.getNextEdge();
            }
            System.out.println();
        }
    }
}

class Edge {
    // 边的权重
    private int weight;
    // 边的尾部存放的顶点
    private Vertex rearVer;
    // 指向的下条边
    private Edge nextEdge;

    public Edge(int weight, Vertex rearVer) {
        this.weight = weight;
        this.rearVer = rearVer;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public Vertex getRearVer() {
        return rearVer;
    }

    public void setRearVer(Vertex rearVer) {
        this.rearVer = rearVer;
    }

    public Edge getNextEdge() {
        return nextEdge;
    }

    public void setNextEdge(Edge nextEdge) {
        this.nextEdge = nextEdge;
    }
}

class Vertex {
    // 顶点的值
    private int verVal;
    // 边链表的头结点
    private Edge edgeHead;
    // 标记该顶点是否被访问过
    private boolean isVisited;

    public boolean getIsVisited() {
        return isVisited;
    }

    public void setIsVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }

    public Vertex(int verVal) {
        this.verVal = verVal;
    }

    public int getVerVal() {
        return verVal;
    }

    public void setVerVal(int verVal) {
        this.verVal = verVal;
    }

    public Edge getEdgeHead() {
        return edgeHead;
    }

    public void setEdgeHead(Edge edgeHead) {
        this.edgeHead = edgeHead;
    }
}